package practice;

import java.util.*;

public class Day35 {
    //单词搜索
    public boolean exist(char[][] board, String word) {
        int n = board.length;
        int m = board[0].length;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (dfs(board, i, j, 0, word.toCharArray())) {
                    return true;
                }
            }
        }
        return false;
    }

    private boolean dfs(char[][] board, int i, int j, int k, char[] word) {


        if (i >= board.length || j >= board[0].length || i < 0 || j < 0 ||
                board[i][j] != word[k]) {
            return false;
        }
        if (k == word.length - 1) {
            return true;
        }
        board[i][j] = ' ';

        boolean ret = dfs(board, i + 1, j, k + 1, word) || dfs(board, i - 1, j, k + 1, word)
                || dfs(board, i, j + 1, k + 1, word) || dfs(board, i, j - 1, k + 1, word);
        board[i][j] = word[k];
        return ret;
    }

    //分割字符串
    List<List<String>> list = new ArrayList<>();
    List<String> path = new ArrayList<>();
    String s;
    public List<List<String>> partition(String s) {
        if(s.length() == 0) {
            return list;
        }
        this.s = s;
        dfs(0,0);
        return list;
    }

    private void dfs(int i, int start) {
        if(i == s.length()) {
            list.add(new ArrayList<>(path));
            return;
        }
        //不选i和i+1之间的逗号,i=n-1必须选，此时表示整个字符串
        if(i < s.length()-1) {
            dfs(i+1,start);
        }

        //选i和i+1之间的逗号
        if(isVaild(s.substring(start,i+1))) {
            path.add(s.substring(start,i+1));
            //遍历i+1后面的字符串，同时设置start位置
            dfs(i+1,i+1);
            path.remove(path.size()-1);
        }
    }
    private boolean isVaild(String str) {
        int left = 0;
        int right = str.length() - 1;
        while(left < right) {
            if(str.charAt(left) != str.charAt(right)) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }

    //总路径和
    private Map<Long,Integer> map;
    public int pathSum(TreeNode root, int targetSum) {
        map = new HashMap<>();
        map.put(0L,1);
        return rootSum(root,0,targetSum);
    }

    private int rootSum(TreeNode root,long sum,int targetSum) {
        if(root == null) {
            return 0;
        }
        sum += root.val;
        int ret = 0;
        ret += map.getOrDefault(sum-targetSum,0);
        map.put(sum,map.getOrDefault(sum,0)+1);
        ret += rootSum(root.left,sum,targetSum);
        ret += rootSum(root.right,sum,targetSum);
        map.put(sum,map.getOrDefault(sum,0)-1);
        return ret;
    }
    //和为k的数组
    public int subarraySum(int[] nums, int k) {
        int count = 0;
        Map<Integer,Integer> map = new HashMap<>();
        map.put(0,1);
        int ret = 0;
        for(int x : nums) {
            count += x;
            ret += map.getOrDefault(count-k,0);
            map.put(count,map.getOrDefault(count,0)+1);
        }
        return ret;
    }
    //螺旋矩阵
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> list = new LinkedList<>();
        if (matrix == null || matrix.length == 0) {
            return list;
        }
        int n = matrix.length;
        int m = matrix[0].length;
        int top = 0;
        int bottom = n - 1;
        int left = 0;
        int right = m - 1;
        while (left <= right && top <= bottom) {
            // 第一行
            for (int i = left; i <= right; i++) {
                list.add(matrix[top][i]);
            }
            // 最后一列
            for (int i = top + 1; i <= bottom; i++) {
                list.add(matrix[i][right]);
            }
            // 最后一行
            for (int i = right - 1; i >= left; i--) {
                list.add(matrix[bottom][i]);
            }
            // 第一列
            for (int i = bottom - 1; i > top; i--) {
                list.add(matrix[i][left]);
            }
            left++;
            top++;
            right--;
            bottom--;
        }
        return list;
    }

    //判断字符是否唯一
    public boolean isUnique(String astr) {
        Set<Character> set = new HashSet<>();
        if(astr.length() == 0) {
            return true;
        }
        set.add(astr.charAt(0));
        for(int i = 1; i < astr.length(); i++) {
            if(set.contains(astr.charAt(i))) {
                return false;
            }
            set.add(astr.charAt(i));

        }
        return true;
    }
    //漂亮数组（分治，递归）
    Map<Integer,int[]> map1 = new HashMap<>();
    public int[] beautifulArray(int n) {
        return fun(n);
    }
    private int[] fun(int n) {
        if(map.containsKey(n)) {
            return map1.get(n);
        }
        int[] ret = new int[n];
        if(n == 1) {
            ret[0] = 1;
        }else {
            int k = 0;
            for(int i : fun((n+1)/2)) {
                ret[k++] = 2 * i-1;
            }
            for(int i : fun(n/2)) {
                ret[k++] = 2 * i;
            }
        }
        map1.put(n,ret);
        return ret;
    }
    //递归乘法
    public int multiply(int A, int B) {
        if(B == 0) {
            return 0;
        }
        return A + multiply(A,B-1);
    }
    //判断字符是否唯一（位运算）
    public boolean isUnique1(String astr) {
        int i = 0;
        for(char ch : astr.toCharArray()) {
            int k = ch - 'a';
            if((i & (1 << k)) != 0) {
                return false;
            }
            i |= (1 << k);
        }
        return true;
    }
    //最短无序连续子数组
    public int findUnsortedSubarray(int[] nums) {
        int left = -1;
        int right = -1;
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        int n = nums.length;
        for(int i = 0; i < n; i++) {
            if(nums[i] < max) {
                right = i;
            }else {
                max = nums[i];
            }

            if(nums[n-i-1] > min) {
                left = n-i-1;
            }else {
                min = nums[n-i-1];
            }
        }
        return left == -1 ? 0 : right - left + 1;
    }
    //螺旋矩阵2
    public int[][] generateMatrix(int n) {
        int[][] ret = new int[n][n];
        int k = 1;
        int left = 0;
        int right = n-1;
        int top = 0;
        int bottom = n-1;
        while(left <= right && top <= bottom) {
            //第一行
            for(int i = left; i <= right; i++) {
                ret[top][i] = k++;
            }
            //最后一列
            for(int i = top+1; i <= bottom; i++) {
                ret[i][right] = k++;
            }
            //最后一行
            for(int i = right-1; i >= left; i--) {
                ret[bottom][i] = k++;
            }
            //第一列
            for(int i = bottom-1; i > top; i--) {
                ret[i][left] = k++;
            }
            left++;
            top++;
            right--;
            bottom--;
        }
        return ret;
    }

    boolean[] flag1;
    boolean[] flag2;
    boolean[] col;
    int[] path1;
    public List<List<String>> solveNQueens(int n) {
        if(n == 0) {
            return list;
        }
        flag1 = new boolean[2*n-1];
        flag2 = new boolean[2*n-1];
        col = new boolean[n];
        path1 = new int[n];
        dfs1(0,n);
        return list;
    }
    private List<String> build(int n) {
        List<String> ret = new ArrayList<>();
        for(int x : path1) {
            char[] arr = new char[n];
            Arrays.fill(arr,'.');
            arr[x] = 'Q';
            ret.add(new String(arr));
        }
        return ret;
    }
    //r代表行标
    private void dfs1(int r,int n) {
        if(n == r) {
            list.add(build(n));
        }

        //c代表列的下标，因为是每一行放一个皇后，所以只需要考虑放哪一列
        for(int c = 0; c < n; c++) {
            //由于r-c有可能是负数，所以需要修正
            //第一个代表列未选，第二个代表右对角上没有皇后，第三个代表左对角线上没有皇后
            if(!col[c] && !flag1[r+c] && !flag2[r-c+n-1]) {
                path1[r] = c; //第r行的第c列
                col[c] = flag1[r+c] = flag2[r-c+n-1] = true;
                dfs1(r+1,n);
                //回溯
                col[c] = flag1[r+c] = flag2[r-c+n-1] = false;
            }
        }
    }

    private int[] dx = {0,0,1,-1};
    private int[] dy = {1,-1,0,0};
    public int orangesRotting(int[][] grid) {
        int count = 0;
        Stack<int[]> stack = new Stack<>();
        int n = grid.length;
        int m = grid[0].length;

        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                if(grid[i][j] == 2) {
                    stack.push(new int[]{i,j});
                }
            }
        }

        //开始遍历
        while(!stack.isEmpty()) {
            int size = stack.size();
            boolean flag = false;
            while(size != 0) {
                int[] top = stack.pop();
                for(int i = 0; i < 4; i++) {
                    int x = top[0] + dx[i];
                    int y = top[1] + dy[i];
                    if(x >= 0 && x < n && y >= 0 && y < m && grid[x][y] == 1) {
                        grid[x][y] = 2;
                        stack.push(new int[]{x,y});
                        flag = true;
                        System.out.println("x: " + x + ",y: " +y);
                    }
                }
                size--;
            }
            if(flag) {
                count++;
            }
        }
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                if(grid[i][j] == 1) {
                    return -1;
                }
            }
        }
        return count;
    }

    public static void main(String[] args) {
        Day35 day35 = new Day35();
        int[][] arr = new int[4][1];
        arr[0][0] = 1;
        arr[1][0] = 2;
        arr[2][0] = 1;
        arr[3][0] = 2;
        day35.orangesRotting(arr);
    }

    //二分查找
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length-1;
        while(left <= right) {
            int mid = (right - left) / 2 + left;
            if(nums[mid] == target) {
                return mid;
            }
            if(nums[left] <= nums[mid]) {
                if(target < nums[mid] && target >= nums[left]) {
                    right = mid - 1;
                }else {
                    left = mid + 1;
                }
            }else {
                if(nums[right] >= target && target > nums[mid]) {
                    left = mid + 1;
                }else {
                    right = mid - 1;
                }
            }
        }
        return -1;
    }
    //跳跃游戏
    public boolean canJump(int[] nums) {
        int n = nums.length;
        int max = Integer.MIN_VALUE;
        int left = 0;
        int right = 0;
        while (left <= right) {
            for (int i = left; i <= right; i++) {
                max = Math.max(max, i + nums[i]);
                if (max >= n - 1) {
                    return true;
                }
                left = right + 1;
                right = max;
            }
        }
        return false;
    }
}
